package com.dubious.interview.euler.prime;

import com.dubious.interview.euler.booleans.BitSetBooleans;
import com.dubious.interview.euler.booleans.Booleans;

/**
 * Iterates over prime numbers using the Sieve of Eratosthenes.
 * Has been shown to work with an upper bound of 10,000,000 in less than 60 minutes with a heap 
 * of 1024M.
 */
public class SievePrimeIterator extends PrimeIterator {

    // TODO: Optimizations to consider for memory usage:
    // - use long instead of Long?
    // - don't track multiples of 2,3,5,7,11...
    // - rebuild prime array in stages

    private long upperBound = 0;
    private Booleans isNotPrime = null;
        
    public SievePrimeIterator(long upperBound)
    {
        this.upperBound = upperBound;
        isNotPrime = new BitSetBooleans(upperBound/2);
    }
    
    @Override
    protected long nextPrime()
    {
        long lastPrime = getLastPrime();
        long nextPrime = lastPrime;
        if(lastPrime < 3)
        {            
            // handling of 1 => 2
            if(upperBound <= lastPrime + 1)
            {
                return 0;
            } else if(lastPrime <= 1)
            {
                return lastPrime + 1;
            }
            
            // 2 => 3
            nextPrime = 3;
        } else
        {
            // here we can assume candidatePrimes will be odd and greater than 3
            while(true)
            {
                nextPrime += 2;
                if(nextPrime >= upperBound)
                {
                    return 0;
                }
                
                if (!isNotPrime.get(nextPrime / 2)) {
                    break;
                }
            }
        }
        
        // mark as "not prime" odd multiples of i greater than i^2
        // NOTE we start from i^2 instead of i.  It is a known optimization
        // though please don't ask me to explain why.
        
        // we also can increment by 2*i thus ensuring we are treating only odd multiples 
        for (long j = (long)Math.pow(nextPrime, 2); j < upperBound; j += nextPrime) {
            if(j % 2 == 1)
            {
                isNotPrime.set(j / 2, true);
            }
        }

        return nextPrime;
    }
    
}
